//
// Created by wjf82 on 2020/6/7.
//

#include "sudoku_new.h"

extern int normal[MAXNU];

int normal[MAXNU] = {1,2,3,4,5,6,7,8,9};

//查找空单元并返回位置
Local find_zero_local(int arr[MAXNU][MAXNU])
{
    Local local = {0,0};
    int flag = 0;
    for (int x = 0; x < MAXNU; ++x) {
        for (int y = 0; y < MAXNU; ++y) {
            if(arr[x][y] == 0) {
                local.x = x+1;
                local.y = y+1;
                flag = 1;
                break;
            }
        }
        if(flag)
            break;
    }
    return local;
}

//判断是否有空单元
bool had_zero_uint(int arr[MAXNU][MAXNU])
{
    Local l_tem;
    l_tem = find_zero_local(arr);
    if(l_tem.x == 0 && 0 == l_tem.y){
        return false;
    } else{
        return ture;
    }
}

//输出数独
void output_sudoku(int arr_sudoku[][MAXNU])
{
    //输出整个数独
    printf("\n");
    for (int i = 0; i < MAXNU; ++i) {
        for (int j = 0; j < MAXNU; ++j) {
            printf("%d  ",arr_sudoku[i][j]);
            if((j+1) % 3 == 0){
                printf("  ");
            }
        }
        if((i+1) % 3 == 0){
            printf("\n");
        }
        printf("\n");
    }
}

//输入后求解前判断是否满足数独条件
bool is_input_error(int arr[MAXNU][MAXNU])
{
    if(is_sudoku_line(arr)){               //行判断
        if(is_sudoku_row(arr)){            //列判断
            if(is_sudoku_square(arr)){     //组判断
                return false;
            }
        } else return ture;
    } else return  ture;
    return ture;
}

//根据所在行判断是否满足没有重复元素的要求
bool is_sudoku_line(int arr[MAXNU][MAXNU])
{
    //判断行相同
    for (int i = 0; i < MAXNU; ++i) {
        for (int j = 0; j < MAXNU; ++j) {
            for (int k = j + 1; k < MAXNU; ++k) {
                if(arr[i][j] == arr[i][k] && arr[i][j] != 0){
                    //行相同 非数独
#ifdef DEBUG
                    printf("The line %d had a same number %d.It's not a sudoku!\n",i+1,arr[i][j]);
#endif
                    return false;
                }
            }
        }
    }
    return ture;
}

//根据所在列判断是否满足没有重复元素的要求
bool is_sudoku_row(int arr[MAXNU][MAXNU])
{
    //判断列相同
    for (int j = 0; j < MAXNU; ++j) {
        for (int i = 0; i < MAXNU; ++i) {
            for (int k = i+1; k < MAXNU; ++k) {
                if(arr[i][j] == arr[k][j] && arr[i][j] != 0){
                    //列相同 非数独
#ifdef DEBUG
                    printf("The row %d had a same number %d.It's not a sudoku!\n",j+1,arr[i][j]);
#endif
                    return false;
                }
            }
        }
    }
    return ture;
}

//获得宫格组的二维数组并将数据存放到res[][]里
void get_square_arr(int arr[MAXNU][MAXNU],int res[MAXNU][MAXNU])
{
    struct sqr_nu{
        int nu1;    //第1-9个宫格
        int nu2;
        int nu3;
        int nu4;
        int nu5;
        int nu6;
        int nu7;
        int nu8;
        int nu9;
    }sqrNu = {0,0,0,0,0,0,0,0,0};

    //将所有数组元素分宫格
    for (int x = 0; x < MAXNU; ++x) {
        for (int y = 0; y < MAXNU; ++y) {

            if(x>=0 && x < 3 && y>=0 && y<3){   //第一宫格
                res[0][sqrNu.nu1++] = arr[x][y];
            } else if(x>=0 && x < 3 && y>=3 && y<6){   //第二宫格
                res[1][sqrNu.nu2++] = arr[x][y];
            }else if(x>=0 && x < 3 && y>=6 && y<9){   //第三宫格
                res[2][sqrNu.nu3++] = arr[x][y];
            }else if(x>=3 && x < 6 && y>=0 && y<3){   //第四宫格
                res[3][sqrNu.nu4++] = arr[x][y];
            }else if(x>=3 && x < 6 && y>=3 && y<6){   //第五宫格
                res[4][sqrNu.nu5++] = arr[x][y];
            }else if(x>=3 && x < 6 && y>=6 && y<9){   //第六宫格
                res[5][sqrNu.nu6++] = arr[x][y];
            }else if(x>=6 && x < 9 && y>=0 && y<3){   //第七宫格
                res[6][sqrNu.nu7++] = arr[x][y];
            }else if(x>=6 && x < 9 && y>=3 && y<6){   //第八宫格
                res[7][sqrNu.nu8++] = arr[x][y];
            }else{                                    //第九宫格
                res[8][sqrNu.nu9++] = arr[x][y];
            }
        }
    }
}

//获得所在宫格号
int get_square_nu(int x,int y)
{
    if(x>=0 && x < 3 && y>=0 && y<3){   //第一宫格
        return 1;
    } else if(x>=0 && x < 3 && y>=3 && y<6){   //第二宫格
        return 2;
    }else if(x>=0 && x < 3 && y>=6 && y<9){   //第三宫格
        return 3;
    }else if(x>=3 && x < 6 && y>=0 && y<3){   //第四宫格
        return 4;
    }else if(x>=3 && x < 6 && y>=3 && y<6){   //第五宫格
        return 5;
    }else if(x>=3 && x < 6 && y>=6 && y<9){   //第六宫格
        return 6;
    }else if(x>=6 && x < 9 && y>=0 && y<3){   //第七宫格
        return 7;
    }else if(x>=6 && x < 9 && y>=3 && y<6){   //第八宫格
        return 8;
    }else{                                    //第九宫格
        return 9;
    }

}

//根据所在列判断是否满足没有重复元素的要求
bool is_sudoku_square(int arr[MAXNU][MAXNU])
{
    int res[MAXNU][MAXNU] = {0};
    get_square_arr(arr,res);
    //判断每个宫格里有没有相同元素
    for (int x = 0; x < MAXNU; ++x) {
        for (int y = 0; y < MAXNU; ++y) {
            for (int i = y+1; i < MAXNU; ++i) {
                if(res[x][y] == res[x][i] && res[x][y] != 0)
                {
                    //宫格内相同 非数独
#ifdef DEBUG
                    int n = get_square_nu(x,y);
                    printf("There had a same number %d in sqare %d.It's not a sudoku!\n",res[x][y],n+1);
                    //输出整个宫格的数独
                    printf("Square:");
                    output_sudoku(res);
#endif
                    return false;
                }
            }
        }
    }

    return ture;
}

//两数组求异 与标准数组normal做对比求异结果放在res[]里
void arr_different(const int arr[],const int nor[], int res[])
{
    //                [5 0 6 4 1 2 9 8 7]
    //                [0,1,2,3,4,5,6,7,8]
    //normal[MAXNU] = {1,2,3,4,5,6,7,8,9};
    int tem[MAXNU] = {0};
    int cnt = 0;
    for (int i = 0; i < MAXNU; ++i) {
        for (int j = 0; j < MAXNU; ++j) {
            if (arr[i] == nor[j]){
                tem[j] = 1;
            }
        }
    }

    for (int i = 0; i < MAXNU; ++i) {
        //printf("%d ",arr[i]);
        if (tem[i] == 0){
            res[cnt++] = i+1;
        }
    }
}

//求所在local_x行的解集
void resolve_sudoku_line(int arr[][MAXNU],const int local_x,int res[])
{
    arr_different(arr[local_x-1],normal,res);
}

//求所在local_y列的解集
void resolve_sudoku_row(int arr[][MAXNU],int local_y,int res[])
{
    //                [5 0 6 4 1 2 9 8 7]
    //                [0,1,2,3,4,5,6,7,8]
    //normal[MAXNU] = {1,2,3,4,5,6,7,8,9};
    int tem[MAXNU] = {0};
    int cnt = 0;
    for (int i = 0; i < MAXNU; ++i) {
        for (int j = 0; j < MAXNU; ++j) {
            if (arr[i][local_y-1] == normal[j]){
                tem[j] = 1;
            }
        }
    }

    for (int i = 0; i < MAXNU; ++i) {
        if (tem[i] == 0){
            res[cnt++] = i+1;
        }
    }
}

//求所在square_n组的解集
void resolve_sudoku_square(int arr[][MAXNU], int square_n,int res[])
{
    int sqr[MAXNU][MAXNU] = {0};
    get_square_arr(arr,sqr);
    arr_different(sqr[square_n-1],normal,res);
}

//求x,y坐标下的可能解集
void resolve_sudoku(int arr[][MAXNU],int x,int y,int res[])
{
    struct resolve_arr{
        int arrline[MAXNU];
        int arrrow[MAXNU];
        int arrsquare[MAXNU];
    }resolveArr = {0,0,0};

    resolve_sudoku_line(arr,x,resolveArr.arrline);
    resolve_sudoku_row(arr,y,resolveArr.arrrow);
    resolve_sudoku_square(arr,get_square_nu(x-1,y-1),resolveArr.arrsquare);

    int addarr[MAXNU*3] = {0};
    int tem[MAXNU] = {0};
    int cnt = 0;
    for (int i = 0; i < MAXNU*3; ++i) {
        if (i < MAXNU){
            addarr[i] = resolveArr.arrline[i];
        } else if(i < MAXNU * 2 && i >= MAXNU){
            addarr[i] = resolveArr.arrrow[i-MAXNU];
        } else{
            addarr[i] = resolveArr.arrsquare[i-MAXNU*2];
        }
    }

    for (int i = 0; i < MAXNU * 3; ++i) {
        for (int j = 0; j < MAXNU; ++j) {
            if(addarr[i] == normal[j]){
                tem[j] ++;
            }
        }
    }

    for (int i = 0; i < MAXNU; ++i) {
        if(tem[i] == 3){
            res[cnt++] = normal[i];
        }
    }
    //把剩余的res[]用0填满,以免出现重复结果
    //相当于初始化
    for (int i = cnt; i < MAXNU; ++i) {
        res[cnt++] = 0;
    }

#ifdef DEBUG
    printf("\n");

    printf("res[]:\n");
    for (int i = 0; i < MAXNU; ++i) {
        printf("%d ",res[i]);
    }
    printf("\n");
#endif
}

//是否能满足数独的四个条件
//1.没有空单元 2.行元素各不同 3.列元素各不同 4.组元素各不同
bool is_sudoku(int arr[][MAXNU])
{
    if(!had_zero_uint(arr)){                    //空判断
        if(is_sudoku_line(arr)){               //行判断
            if(is_sudoku_row(arr)){            //列判断
                if(is_sudoku_square(arr)){     //组判断
                    return ture;
                }
            } else return false;
        } else return  false;
    } else return false;

    return false;
}

//判断解集数组是否为空
bool is_nop_arr(const int arr[])
{
    int cnt = 0;
    for (int i = 0; i < MAXNU; ++i) {
        if(arr[i] == 0){
            cnt ++;
        }
    }
    if(cnt >= 9){
        return ture;
    } else{
        return false;
    }
}

//删除数组中的第一个元素
void delete_arr_first(int arr[])
{
    for (int i = 0; i < MAXNU; ++i) {
        arr[i] = arr[i+1];
    }
    arr[MAXNU-1] = 0;
}

//打印一个一维数组
void print_arr(int arr[])
{
    printf("arr[]:\n");
    for (int i = 0; i < MAXNU; ++i) {
        printf("%d ",arr[i]);
    }
    printf("\n");
}

//打印一个m行n列的数组
void outprint_arr(int m,int n,int arr[m][n])
{
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            printf("%d ",arr[i][j]);
        }
        printf("\n");
    }
}

//找出所有空单元返回个数 将坐标记录到res[n][1]和res[n][2]中 res[n][0]标记是否为空
int find_all_zero(int arr[MAXNU][MAXNU],int res[MAXNU*MAXNU][3])
{
    int count = 0;
    int isZero = 0;
    for (int x = 0; x < MAXNU; ++x) {
        for (int y = 0; y < MAXNU; ++y) {
            if(arr[x][y] != 0){
                res[count][0] = 1;
                res[count][1] = x;
                res[count][2] = y;
                count++;
            }else{
                res[count][0] = 0;
                res[count][1] = x;
                res[count][2] = y;
                count++;
                isZero++;
            }
        }
    }
    return isZero;
}

//根据填入空单元的序号返回坐标
Local count_find_local(int arr[MAXNU*MAXNU][3],int count)
{
    Local cnt_l = {0,0};
    for (int i = 0; i < MAXNU*MAXNU; ++i) {
        if(arr[i][0] == 0)
        {
            count--;
            if(count == 0){
                cnt_l.x = arr[i][1];
                cnt_l.y = arr[i][2];
                break;
            }
        }
    }

    return cnt_l;
}

//根据坐标返回空坐标的序号
int local_find_count(int x,int y,int arr[MAXNU*MAXNU][3])
{
    int n = 0;
    for (int i = 0; i < MAXNU * MAXNU; ++i) {
        if(arr[i][0] == 0){
            n ++;
            if(x == arr[i][1] && y == arr[i][2]){
                break;
            }
        }
    }

    return n;
}

//求所有空单元的解集 对应第N个 存放在二维数组里
void resolve_all_arr(int arr[MAXNU][MAXNU],int res[MAXNU*MAXNU][MAXNU])
{
    int tem[MAXNU*MAXNU][3] = {0};
    int result[MAXNU] = {0};
    int cnt = 0,count = 0;
    cnt = find_all_zero(arr,tem);

//    outprint_arr(MAXNU*MAXNU,3,tem);

    for (int i = 0; i < MAXNU*MAXNU; ++i) {
        if(tem[i][0] == 0){
            resolve_sudoku(arr,tem[i][1]+1,tem[i][2]+1,result);
            for (int j = 0; j < MAXNU; ++j) {
                res[i][j] = result[j];
            }
        }
    }

}

//删除空单元解集的n行的第一个解 并恢复其后的其他解 将结果储存在res[][]中
void delete_one_key(int n,int arr[MAXNU*MAXNU][MAXNU],int res[MAXNU*MAXNU][MAXNU])
{
    int temp[MAXNU*MAXNU][MAXNU] = {0};

    //复制解集
    for (int i = 0; i < MAXNU*MAXNU; ++i) {
        for (int j = 0; j < MAXNU; ++j) {
            temp[i][j] = arr[i][j];
        }
    }

    //删除第x行y列的第一个解
    delete_arr_first(temp[n]);

    //
    for (int i = 0; i < MAXNU*MAXNU; ++i) {
        for (int j = 0; j < MAXNU; ++j) {
            res[i][j] = temp[i][j];
        }
    }
}

//将一个一维数组写入二维数组的第n行
void write_one_to_two(int n,const int arr[MAXNU],int res[MAXNU*MAXNU][MAXNU])
{
    for (int i = 0; i < MAXNU; ++i) {
        res[n][i] = arr[i];
    }
}

//将第n行的二维数组写入一维数组
void write_two_to_one(int n,int arr[MAXNU*MAXNU][MAXNU],int res[MAXNU])
{
    for (int i = 0; i < MAXNU; ++i) {
        res[i] = arr[n][i];
    }
}

//更便捷的输入方式
void input_sudoku_new(int arr[][MAXNU])
{
    char input[MAXNU] = "";
    for (int i = 0; i < MAXNU; ++i) {
        printf("Please input 9 numbers for line %d:\n",i+1);
        scanf("%s",&input);
        for (int j = 0; j < MAXNU; ++j) {
            arr[i][j] = (int)input[j];
        }
    }

//    for (int i = 0; i < MAXNU; ++i) {
//        for (int j = 0; j < MAXNU; ++j) {
//
//        }
//    }
}
